package leetcode.editor.cn;

//给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：6
//解释：最大矩形如上图所示。
// 
//
// 示例 2： 
//
// 
//输入：matrix = []
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：matrix = [["0"]]
//输出：0
// 
//
// 示例 4： 
//
// 
//输入：matrix = [["1"]]
//输出：1
// 
//
// 示例 5： 
//
// 
//输入：matrix = [["0","0"]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// rows == matrix.length 
// cols == matrix[0].length 
// 1 <= row, cols <= 200 
// matrix[i][j] 为 '0' 或 '1' 
// 
// Related Topics 栈 数组 动态规划 矩阵 单调栈 👍 1257 👎 0

import java.util.Arrays;
import java.util.Stack;

//Java：【85】 - 最大矩形
public class MaximalRectangle_85{
    public static void main(String[] args) {
        Solution solution = new MaximalRectangle_85().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int[][] heights = new int[matrix.length][matrix[0].length+2];
        // 构造每一行的高度，同时两边补0
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == '1')
                    heights[i][j+1] = (i==0?0:heights[i-1][j+1])+1;
            }
        }
        // 同【84】思路
        int res =0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < heights[0].length; j++) {
                while (!stack.isEmpty() && heights[i][j]<heights[i][stack.peek()]){
                    int h = heights[i][stack.pop()];
                    res = Math.max(res, h*(j-stack.peek()-1));
                }
                stack.push(j);
            }
            stack.clear();
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
